# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, t, k):
        # write code here
        n = len(t)
        if n == 0 or k <= 0 or k > n:
            return []
        m = self.heapSort(t)
        return m

    def heapSort(self, t):
        if t == None or len(t) < 2:
            return
        for i in range(len(t)):
            self.heapInsert(t, i)
        size = len(t) - 1
        self.swap(t, 0, size)
        while size > 0:
            self.heapify(t, 0, size)
            size -= 1
            self.swap(t, 0, size)
        return t

    def heapify(self, arr, index, size):
        left = 2 * index + 1
        while left < size:
            if left + 1 < size and arr[left] > arr[left + 1]:
                l = left + 1
            else:
                l = left
            if arr[index] < arr[l]:
                l = index
            else:
                l = l
            if l == index:
                break
            self.swap(arr, index, l)
            # 找到一个最小值放上去
            index = l
            left = index * 2 + 1
    # 小根
    def heapInsert(self, arr, index):
        while arr[index] < arr[int((index - 1) / 2)]:
            self.swap(arr, index, int((index - 1) / 2))
            index = int((index - 1) / 2)

    def swap(self, arr, i, j):
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp


a = [4,5,1,6,2,7,3,8]
s=Solution()
print(s.GetLeastNumbers_Solution(a,4))